class Solution {
    /**
     * O(n) O(3)
     * @param nums
     */
    public void sortColors(int[] nums) {
        int[] counts = new int[3];
        for (int i : nums) {
            counts[i]++;
        }
        int cur_count = 0;
        for (int i = 0; i < nums.length; i++){
            while (counts[cur_count] == 0) {
                cur_count++;
            }
            nums[i] = cur_count;
            counts[cur_count]--;
        }
    }

    public void sortColorsIterTwice(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; i++){
            if (nums[i] == 0){
                swap(nums, i, ptr);
                ptr++;
            }
        }

        for (int i = 0; i < n; i++){
            if (nums[i] == 1){
                swap(nums, i, ptr);
                ptr++;
            }
        }
    }

    public void sortColorsOneSide(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; i++){
            
            if (nums[i] == 1){
                swap(nums, i, p1);
                p1++;
            } else if (nums[i] == 0) {
                swap(nums, i, p0);
                if (p0 < p1) {
                    // 0 会把已经置换到前面的1 换到i处，重新交换一下，让i进入1区末尾
                    swap(nums, i, p1);
                }
                // 0，1都增加
                p0++;
                p1++;
            }
        }
    }

    public void sortColorsDoubleSide(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n-1;
        for (int i = 0; i <= p2; i++){
            while (i <= p2 && nums[i] == 2){ // 交换后仍可能为2，故不断交换
                swap(nums, i, p2);
                p2--;
            }
            if (nums[i] == 0){
                swap(nums, i, p0);
                p0++;
            }
        }
    }

    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}